package com.jia.leetCode;

import java.util.Arrays;

public class Pro5477 {
    public int minSwaps(int[][] grid) {
        int n = grid.length;
        int[] rowZeros = new int[n];

        for(int r = 0; r < n; r++) {
            int countZeros = 0;
            for(int c = n-1; c>0; c--) {
                if(grid[r][c] == 0) {
                    ++countZeros;
                }else {
                    break;
                }
            }
            rowZeros[r] = countZeros;
        }
        int[] tmp = Arrays.copyOf(rowZeros, n);
        Arrays.sort(tmp);
        for(int i = 0; i < n; i++) {
            if(tmp[i]<i) {return - 1;}
        }
        int ans = 0;
        for(int i = 0; i < rowZeros.length; i++) {
            int zeros = n - i - 1;
            for(int j = i; j < rowZeros.length; j++) {
                if(zeros <= rowZeros[j]) {
                    if(i == j) {break;}
                    ans += (j - i);
                    while(j > i) {rowZeros[j] = rowZeros[j-1]; --j;}
                    rowZeros[i] = zeros;
                    break;
                }
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        Pro5477 pro5477 = new Pro5477();
        int[][] grid = {{1,0,0},{1,1,0},{1,1,1}};
        System.out.println(pro5477.minSwaps(grid));
    }
}
